home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 22 / Cream of the Crop 22.iso / program / snpd9611.zip / ETPHI.C < prev    next >
C/C++ Source or Header  |  1996-11-24  |  1KB  |  91 lines
  1. /* +++Date last modified: 17-Nov-1996 */
  2.  
  3. /*
  4. **  ETPHI.c
  5. **
  6. **  Compute Euler's Totient function, phi().
  7. **  phi(n) = the number of positive integers less than n
  8. **  which have no common factors with n
  9. **
  10. **  Written by M. Stapleton of Graphic Bits
  11. **  Public Domain
  12. **
  13. **  Sep  7 1996
  14. **
  15. **  Uses ISQRT.C, also in SNIPPETS
  16. */
  17.  
  18. #include "snipmath.h"
  19.  
  20. #undef ULONG
  21. typedef unsigned long ULONG;
  22.  
  23. ULONG intsqrt(ULONG n);
  24.  
  25. static void dofact(ULONG i);
  26. ULONG etphi(ULONG n);
  27.  
  28. static ULONG num, ph;
  29.  
  30. void dofact(ULONG i)
  31. {
  32.       long p;
  33.  
  34.       for (p = 0; (num % i) == 0; p++)
  35.             num /= i;
  36.  
  37.       if (p)
  38.       {
  39.             ph *= i - 1;
  40.             while(--p)
  41.                   ph *= i;
  42.       }
  43. }
  44.  
  45. ULONG etphi(ULONG n)
  46. {
  47.       ULONG i;
  48.       struct int_sqrt mi;
  49.  
  50.       if (n<2)
  51.             return 0;
  52.  
  53.       num = n;
  54.       ph = 1;
  55.       usqrt(n, &mi);
  56.  
  57.       dofact(2);
  58.       dofact(3);
  59.       for (i = 5; (i <= mi.sqrt) && (num >= i); i += 6)
  60.       {
  61.             dofact(i);
  62.             if (num < i + 2)
  63.                   break;
  64.             dofact(i + 2);
  65.       }
  66.  
  67.       if (num > 1)
  68.             ph *= num - 1;
  69.  
  70.       return ph;
  71. }
  72.  
  73. #ifdef TEST
  74.  
  75. #include <stdlib.h>
  76. #include <stdio.h>
  77.  
  78. int main(int argc, char *argv[])
  79. {
  80.       long n = 0;
  81.  
  82.       if (argc > 1)
  83.             n = atol(argv[1]);
  84.  
  85.       printf("etphi(%ld) = %ld\n", n, etphi(n));
  86.  
  87.       return 0;
  88. }
  89.  
  90. #endif
  91.